#include <iostream>
#include <string>
using namespace std;
// 不带头结点的链表队列
class Queue {
    struct Node {
        char val;
        Node* next;
        Node() : val{}, next{nullptr} {}
        Node(char _val) : val{_val}, next{nullptr} {}
    };
    Node* head = nullptr;
    Node* tail = nullptr;
public:
    Queue() {}
    Queue(string s) {
        for (const auto& c : s) {
            enQueue(c);
        }
    }
    ~Queue() {
        while (not empty()) {
            deQueue();
        }
    }

    bool empty() {
        return not head;
    }

    void enQueue(char val) {
        if (empty()) {
            head = new Node(val);
            tail = head;
            return;
        }
        tail->next = new Node(val);
        tail = tail->next;
    }

    char deQueue() {
        if (empty()) {
            perror("empty!\n");
            return -1;
        }
        if (not head->next) {
            char res = head->val;
            delete head;
            head = tail = nullptr;
            return res;
        }
        Node* node = head;
        char res = node->val;
        head = head->next;
        delete node;
        return res;
    }

    char top() {
        if (empty()) return -1;
        return head->val;
    }
};

int main() {
    Queue q;
    q.enQueue('a');
    q.enQueue('b');
    q.enQueue('c');
    q.enQueue('d');
    q.enQueue('e');
    q.enQueue('f');
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
}
